/**
 * @author hewei
 * @version 1.0
 * @description: 935. 骑士拨号器
 * @date 2022/9/21 15:27
 */

public class KnightDialer {

    public int knightDialer(int n) {
        long[][] dp = new long[n][10];
        int mod = (int) (1e9 + 7);
        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][4] + dp[i - 1][6];
            dp[i][1] = dp[i - 1][6] + dp[i - 1][8];
            dp[i][2] = dp[i - 1][7] + dp[i - 1][9];
            dp[i][3] = dp[i - 1][4] + dp[i - 1][8];
            dp[i][4] = dp[i - 1][3] + dp[i - 1][0] + dp[i - 1][9];
            dp[i][6] = dp[i - 1][1] + dp[i - 1][7] + dp[i - 1][0];
            dp[i][7] = dp[i - 1][6] + dp[i - 1][2];
            dp[i][8] = dp[i - 1][3] + dp[i - 1][1];
            dp[i][9] = dp[i - 1][2] + dp[i - 1][4];
            for (int j = 0; j < 10; j++) {
                dp[i][j] %= mod;
            }
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dp[n - 1][i];
            ans %= mod;
        }
        return (int) (ans % mod);
    }
}

